#include <iostream>
#include <fstream>
#include <cstdlib>
#include <list>
#include <cmath>
#include "mpi.h"

using namespace std;

#define CHECK_MSG_AMOUNT 5000

#define MSG_WORK_REQUEST 1000
#define MSG_WORK_SENT    1001
#define MSG_WORK_NOWORK  1002
#define MSG_BEST		 1003
#define MSG_FINISH       1004

#define LENGTH			 1000

MPI_Status status;

char buffer[LENGTH];
int position = 0;

typedef struct Stav {
	bool* konfigurace;
	int nezavisle;
	int ukazatel;
	int max;
	
	Stav(){
		konfigurace = NULL;
	}

	Stav(int pocet){
		konfigurace = new bool[pocet];
		for(int i = 0; i < pocet; i++){
			konfigurace[i] = false;
		}
		max = pocet;
		nezavisle = 0;
		ukazatel = 0;
	}

	~Stav(){
		delete [] konfigurace;
	}
	
	void nastav(Stav* stav_pointer){
		for(int i = 0; i < max; i++){
			konfigurace[i] = stav_pointer->konfigurace[i];
		}
		max = stav_pointer->max;
		nezavisle = stav_pointer->nezavisle;
		ukazatel = stav_pointer->ukazatel;
	}

	void vypis(){
		for(int i = 0; i < max; i++){
			cout << konfigurace[i];
		}
		cout << "|" << nezavisle;
	}

	bool jeMozny(bool** body){
		for(int i = 0; i < max; i++){
			if(body[ukazatel - 1][i] && konfigurace[i])
				return false;
		}
		return true;
	}

	void push(bool jak){
		if(ukazatel < max){
			konfigurace[ukazatel] = jak;
			ukazatel++;
			if(jak){
				nezavisle++;
			}	
		}
	}

	void pop(){
		ukazatel--;
		if(konfigurace[ukazatel]) nezavisle--;
		konfigurace[ukazatel] = NULL;
	}

	void invalidate(){
		ukazatel = max + 1;
	}

	bool isValid(){
		if(ukazatel > max) return false;
		else return true;
	}

	void prijmi(){
		MPI_Recv(buffer, LENGTH, MPI_PACKED, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
		unpack();
	}

	void pack(){
		position = 0;
		MPI_Pack(&nezavisle, 1, MPI_INT, buffer, LENGTH, &position, MPI_COMM_WORLD);
		MPI_Pack(&ukazatel, 1, MPI_INT, buffer, LENGTH, &position, MPI_COMM_WORLD);
		MPI_Pack(&max, 1, MPI_INT, buffer, LENGTH, &position, MPI_COMM_WORLD);
		MPI_Pack(konfigurace, max, MPI_CHAR, buffer, LENGTH, &position, MPI_COMM_WORLD);
	}

	void unpack(){
		position = 0;
		MPI_Unpack(buffer, LENGTH, &position, &nezavisle, 1, MPI_INT, MPI_COMM_WORLD);
		MPI_Unpack(buffer, LENGTH, &position, &ukazatel, 1, MPI_INT, MPI_COMM_WORLD);
		MPI_Unpack(buffer, LENGTH, &position, &max, 1, MPI_INT, MPI_COMM_WORLD);
		MPI_Unpack(buffer, LENGTH, &position, konfigurace, max, MPI_CHAR, MPI_COMM_WORLD);
	}

} Stav;

class myStack{
public:
	int max_pocet;

	myStack(int pocet_bodu){
		stavy = new Stav[pocet_bodu];
		aktualni_pocet = 0;
		max_pocet = pocet_bodu;
	}

	~myStack() {
		delete [] stavy;
	}

	void push(Stav* stav_local){
		if(aktualni_pocet < max_pocet){
			if(stavy[aktualni_pocet].konfigurace) delete [] stavy[aktualni_pocet].konfigurace; 
			stavy[aktualni_pocet].konfigurace = new bool[max_pocet];
			
			for(int i = 0; i < max_pocet; i++){
				stavy[aktualni_pocet].konfigurace[i] = stav_local->konfigurace[i];	
			}
			stavy[aktualni_pocet].nezavisle = stav_local->nezavisle;
			stavy[aktualni_pocet].ukazatel = stav_local->ukazatel; 
			stavy[aktualni_pocet].max = stav_local->max;
			aktualni_pocet++;
		}
		else{
			cout << "Error: preteceni zasobniku" << endl;
			throw 1;
		}
	}

	void pop(){
		if(aktualni_pocet == 0){
			cout << "Error: podteceni zasobniku" << endl;
			throw 1;
		}
		else{
			aktualni_pocet--;
		}
	}

	Stav* top(){
		if(aktualni_pocet == 0){
			cout << "Error: prazdny zasobnik" << endl;
			throw 1;
		}
		else{
			return &stavy[aktualni_pocet - 1];
		}
	}

	Stav* atIndex(int index){
		if(index < 0 || index >= max_pocet){
			cout << "Error: index mimo rozsah" << endl;
			throw 1;
		}
		else{
			return &stavy[index];
		}
	}

	bool hasValid(){
		for(int i = 0; i < aktualni_pocet; i++){
			if(stavy[i].isValid()){
				return true;
			}
		}
		return false;
	}

	int firstValid(){
		for(int i = 0; i < aktualni_pocet; i++){
			if(stavy[i].isValid()){
				return i;
			}
		}
	}

	void invalidateAt(int index){
		if(index < 0 || index >= max_pocet){
			cout << "Error: index mimo rozsah" << endl;
			throw 1;
		}
		else{
			stavy[index].invalidate();
		}
	}

	int size(){
		return aktualni_pocet;
	}

	void empty(){
		aktualni_pocet = 0;
	}

private:
	Stav* stavy;
	int aktualni_pocet;
};
//KONEC: Definice structu pro stav a zasobniku pro stavy

bool** body;

int main(int argc, char* argv[]){
	int rank;
	int procesu;
	int flag;

	MPI_Init(&argc, &argv);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	MPI_Comm_size(MPI_COMM_WORLD, &procesu);

	int pocet_bodu; //Celkovy pocet bodu
	int pocet_hran; //Celkovy pocet hran
	int horni_mez; //Hodnota horni meze
	int dolni_mez; //Hodnota dolni meze
	int max_stupen; //Max stupen bodu
	
	fstream soubor; //Cteme ze souboru

	if (argc < 2) {
		cout << "Error: spatne parametry (jediny parametr je soubor)" << endl;
		MPI_Finalize();
		return 1;
	}

	soubor.open(argv[1]);

	if (!soubor || soubor.eof()){
		cout << "Error: neni soubor, nebo je prazdny" << endl;
		MPI_Finalize();
		return 1;
	}

	soubor >> pocet_bodu; //prvni v souboru je pocet bodu
	body = new bool*[pocet_bodu]; //podle toho alokujeme matici sousednosti
	
	Stav stav = Stav(pocet_bodu); //a take stav
	Stav max_stav = Stav(pocet_bodu); //a maximalni stav
	myStack zasobnik = myStack(pocet_bodu); //zasobnik se stavy k prozkoumani

	pocet_hran = 0;
	horni_mez = 0;
	max_stupen = 0;
	list<int> list_stupnu;
	int soucet_stupnu = 0;
	int stupen_uzlu;
	char bod; //pripravime nacitani po bodu
	for(int i = 0; i < pocet_bodu; i++){
		stupen_uzlu = 0;
		body[i] = new bool[pocet_bodu]; //naalokujeme radek jednoho bodu
		for(int j = 0; j < pocet_bodu; j++){
			soubor >> bod; //nacteme
			if(bod == '1'){
				body[i][j] = true;
				pocet_hran++;
				stupen_uzlu++;
			}
			else if(bod == '0'){
				body[i][j] = false;
			}
		}
		if(stupen_uzlu > max_stupen) max_stupen = stupen_uzlu;
		list_stupnu.push_back(stupen_uzlu);
	}
	pocet_hran = pocet_hran / 2;
	list_stupnu.sort();

	for(list<int>::const_iterator it = list_stupnu.begin(); it != list_stupnu.end(); ++it){
		soucet_stupnu += *it;
		++horni_mez;
		if(soucet_stupnu >= pocet_hran) break;
	}
	dolni_mez = (int)ceil((double)pocet_hran / (double)max_stupen);

	unsigned int citac = 1;
	bool konec = false;
	bool cekaNaNeco = false;
	bool reseniOdeslano = false;
	bool ptatSeTohoCoMel = true;
	int best = 0;
	int cisloDalsiho = -1;
	int realneOdeslano = 0;
	int realnePrijato = 0;
	int max_dotazani = procesu + 1;
	double redukcniFaktor = 0.5;
	bool* bestOd = new bool[procesu];
	int odmitnutiVRade = 0;

	//vytvorime tmp stav
	Stav tmp = Stav(pocet_bodu);

	if(rank == 0){
		zasobnik.push(&stav);
	}

	double t1, t2;
	MPI_Barrier(MPI_COMM_WORLD);
	t1=MPI_Wtime();

	while(!konec){
		if((citac % CHECK_MSG_AMOUNT) == 0){
			MPI_Iprobe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &flag, &status);
			if (flag){
				//prisla zprava, je treba ji obslouzit
				//v promenne status je tag (status.MPI_TAG), cislo odesilatele (status.MPI_SOURCE)
				//a pripadne cislo chyby (status.MPI_ERROR)

				switch(status.MPI_TAG){
					case MSG_WORK_REQUEST:
						//cout << status.MPI_SOURCE << " chce praci od " << rank << endl;
						MPI_Recv(buffer, LENGTH, MPI_PACKED, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
						if(!zasobnik.hasValid()){
							//cout << "praci nedostanes" << endl;
							MPI_Send (buffer, 0, MPI_INT, status.MPI_SOURCE, MSG_WORK_NOWORK, MPI_COMM_WORLD);
							
						}
						else{
							int fi = zasobnik.firstValid();
							tmp.nastav(zasobnik.atIndex(fi));
							//podminka jestli posleme, perspektivnost stavu (neposleme neprespektivni - ztrata)
							if((tmp.max - tmp.ukazatel + tmp.nezavisle) > (tmp.max * redukcniFaktor)){
								//cout << rank << ": posilam " << tmp.max - tmp.ukazatel + tmp.nezavisle << endl;
								zasobnik.invalidateAt(fi);
								tmp.pack();

								//cout << "ok poslu ti"; tmp.vypis();
								MPI_Send (buffer, position, MPI_PACKED, status.MPI_SOURCE, MSG_WORK_SENT, MPI_COMM_WORLD);
							}
							else{
								//cout << "praci nedostanes" << endl;
								MPI_Send (buffer, 0, MPI_INT, status.MPI_SOURCE, MSG_WORK_NOWORK, MPI_COMM_WORLD);	
							}
						}
						cekaNaNeco = false;
						// zadost o praci, prijmout a dopovedet
						// zaslat rozdeleny zasobnik a nebo odmitnuti MSG_WORK_NOWORK
					break;

					case MSG_WORK_SENT:
						//pockame az bude mit mene nez pul (jista rezerva)
						if(zasobnik.size() < (zasobnik.max_pocet / 2)){
							tmp.prijmi();
							zasobnik.push(&tmp);
							//cout << rank << " : prislo mi: "; tmp.vypis(); cout << " -> " << tmp.ukazatel << " nuluji odmitnuti v rade" << endl;
							cekaNaNeco = false;
							realnePrijato++;

							//optame se priste toho co nam ted dal praci?
							if(ptatSeTohoCoMel)
								cisloDalsiho = status.MPI_SOURCE - 1;

							//vynuluji odmitnuti v rade (protoze nas neodmitli)
							odmitnutiVRade = 0;
						}
						else{
							//cout << rank << ": ZS: " << zasobnik.size() << endl; 
						}
						// prisel rozdeleny zasobnik, prijmout
						// deserializovat a spustit vypocet
					break;

					case MSG_WORK_NOWORK: 
						// odmitnuti zadosti o praci
						// zkusit jiny proces 
						// a nebo se prepnout do pasivniho stavu a cekat na token
						MPI_Recv(buffer, LENGTH, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
						odmitnutiVRade++;
						if(odmitnutiVRade < max_dotazani){
							//cout << rank << ": odmitnuti v rade: " << odmitnutiVRade << " max mozne je: " << max_dotazani << endl;
							realnePrijato++;
							cisloDalsiho++;
							if((cisloDalsiho % procesu) == rank)
								cisloDalsiho++;
							
							//cisloDalsiho = status.MPI_SOURCE;
							//cout << rank << ": chce praci od " << (cisloDalsiho % procesu)<< " celkem: " << (realneOdeslano + 1)  << endl;

							MPI_Send (buffer, 0, MPI_INT, (cisloDalsiho % procesu), MSG_WORK_REQUEST, MPI_COMM_WORLD);
							realneOdeslano++;

							cekaNaNeco = true;
						}
						else{
							if(rank != 0){
								if(realneOdeslano == (realnePrijato + 1) && odmitnutiVRade >= max_dotazani && !reseniOdeslano){
									//cout << endl << rank << " zasobnik prazdny a prislo posledni odmitnuti - posilam reseni" << endl;
									//MPI_Recv(buffer, LENGTH, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
									realnePrijato++;
									tmp.nastav(&max_stav);
									tmp.pack();
									MPI_Send (buffer, position, MPI_PACKED, 0, MSG_BEST, MPI_COMM_WORLD);
									reseniOdeslano = true;
									cekaNaNeco = true;
								}
								else{
									//MPI_Recv(buffer, LENGTH, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
									realnePrijato++;
									cekaNaNeco = true;	
								}
							}
							else{
								//MPI_Recv(buffer, LENGTH, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
								realnePrijato++;
								cekaNaNeco = true;
							}
						}										
					break;

					case MSG_FINISH: 
						//konec vypoctu - proces 0 pomoci tokenu zjistil, ze jiz nikdo nema praci
						//a rozeslal zpravu ukoncujici vypocet
						//mam-li reseni, odeslu procesu 0
						//nasledne ukoncim spoji cinnost
						//jestlize se meri cas, nezapomen zavolat koncovou barieru MPI_Barrier (MPI_COMM_WORLD)
						MPI_Recv(buffer, LENGTH, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
						konec = true;
					break;

					case MSG_BEST:
						//prijmam BESTY, ale az na ten posledni, ten az kdyz mam sam dopocitano
						//cout << "prijmam best" << endl;
						if(zasobnik.size() == 0 || best < (procesu - 1)){
							tmp.prijmi();
							if(max_stav.nezavisle < tmp.nezavisle){
								max_stav.nastav(&tmp);
								//cout << endl << "nastavuji: " << tmp.nezavisle << endl;
								//max_stav.vypis();
								//cout << endl;
							}

							if(bestOd[status.MPI_SOURCE] != true){
								best++;
								bestOd[status.MPI_SOURCE] = true;
							}

							cekaNaNeco = true;

							if(best == (procesu - 1)){
								konec = true;
								for(int i = 1; i < procesu; i++){
									MPI_Send (buffer, 0, MPI_INT, i, MSG_FINISH, MPI_COMM_WORLD);	
								}
								delete [] bestOd;
							}
						}
					break;

					default: cout << "Error: neznamy typ zpravy"; break;
				}
			}
			else{
				//nema zpravu, nema praci?
				if(!cekaNaNeco && zasobnik.size() == 0){
					//nemam praci, pozadam nebo poslu reseni na 0
					if(odmitnutiVRade < max_dotazani){
						cisloDalsiho++;
						if((cisloDalsiho % procesu) == rank)
							cisloDalsiho++;
						
						//cout << rank << ": chce praci od " << (cisloDalsiho % procesu) << " celkem: " << (realneOdeslano + 1) << endl;
						
						MPI_Send (buffer, 0, MPI_INT, (cisloDalsiho % procesu), MSG_WORK_REQUEST, MPI_COMM_WORLD);
						
						realneOdeslano++;
						cekaNaNeco = true;
					}
					else{
						if(rank != 0){
							//opravdu na nic neceka?
							if(realneOdeslano == realnePrijato && odmitnutiVRade >= max_dotazani && !reseniOdeslano){
								//cout << rank << ": zeptal jsem se dostatecne procesu a nikdo nedal praci, poslu reseni a pockam na konec" << endl;
								tmp.nastav(&max_stav);
								tmp.pack();
								MPI_Send (buffer, position, MPI_PACKED, 0, MSG_BEST, MPI_COMM_WORLD);
								reseniOdeslano = true;
								cekaNaNeco = true;
							}
						}
						else{
							//cout << rank << ": CNN: " << cekaNaNeco << " BST: " << best << endl;
							cekaNaNeco = true;
						}
					}
				}
			}
		}
		
		citac++;

		//pokud neco v zasobniku je, tak expandujeme
		if(!zasobnik.size() == 0){
			stav.nastav(zasobnik.top()); zasobnik.pop(); //vezmeme ze zasobniku nas stav

			//stav uz nelze dal rozsirovat
			if(stav.ukazatel == stav.max){
				continue;
			}

			//pokud je stav nastaven jako odeslany jinam, neni treba ho resit
			if(!stav.isValid()){
				//cout << rank << ": ignoruji "; stav.vypis(); cout << endl;
				continue;
			}

			//zkusime pridat false
			stav.push(false);

			//ma tento stav cenu? BB dolni hranice
			if(stav.max - stav.ukazatel + stav.nezavisle > max_stav.nezavisle) {
				zasobnik.push(&stav);
			}
			
			//zkusime pridat true
			stav.pop();
			stav.push(true);			

			//jde tento stav pridat?
			if(stav.jeMozny(body) && (stav.max - stav.ukazatel + stav.nezavisle > max_stav.nezavisle)){
				//neni lepsi?
				if(max_stav.nezavisle < stav.nezavisle){
					max_stav.nastav(&stav);
				}
				zasobnik.push(&stav);
			}

			//ma cenu dal pokracovat? //horni bound
			if(max_stav.nezavisle == horni_mez){
				//cout << "Horni bound" << endl;
				zasobnik.empty();
				realneOdeslano = procesu;
				realnePrijato = procesu;
				odmitnutiVRade = max_dotazani;
				cekaNaNeco = false;
				continue;
			}				
		}
		else{
			//osetreni pri spusteni jen na jednom
			if(procesu == 1)
				konec = true;
		}
	}


	MPI_Barrier(MPI_COMM_WORLD);
	t2=MPI_Wtime();

	if(rank == 0){
		cout << "Soubor:  " << argv[1] << endl;
		cout << "Procesu: " << procesu << endl;
		cout << "Reseni: " << endl;
		max_stav.vypis();
		cout << endl << "Spotrebovany cas je " << (t2-t1) << endl;
	}

	MPI_Finalize();
	return 0;
}